<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="utf-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1">
  <title>二叉树的非递归遍历 - lclei blog</title>
  <meta name="renderer" content="webkit" />
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1"/>

<meta http-equiv="Cache-Control" content="no-transform" />
<meta http-equiv="Cache-Control" content="no-siteapp" />

<meta name="theme-color" content="#f8f5ec" />
<meta name="msapplication-navbutton-color" content="#f8f5ec">
<meta name="apple-mobile-web-app-capable" content="yes">
<meta name="apple-mobile-web-app-status-bar-style" content="#f8f5ec">


<meta name="author" content="lclei" /><meta name="description" content="二叉树的遍历有前序，中序，后序以及层次遍历，其中前序，中序和后序遍历使用递归来写非常简单。 例如
1 2 3 4 5 6 7  void tree_preorder_re(TreeNode *node, Tree *tree, void (*visit)(Tree *, TreeNode *)) { if (!node) return; visit(tree, node); tree_preorder_re(node-&amp;gt;left, tree, visit); tree_preorder_re(node-&amp;gt;right, tree, visit); }   中序和后序，不过是调整一下visit的位置，如果不用递归的写法，改用栈来实现，其实没有那么直观。 首先按照函数调用的关系，入栈的套路都是一样的。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18  Stack *s = stack_new(); TreeNode *tNode = tree-&amp;gt;root; while (stack_depth(s) != 0 || tNode) { while (tNode != NULL) { stack_push(s, tNode); tNode = tNode-&amp;gt;left; } if (!stack_is_empty(s)) { tNode = (TreeNode *)stack_pop(s); tNode = tNode-&amp;gt;right; } } stack_free(s);   " /><meta name="keywords" content="lclei, blog, code" />






<meta name="generator" content="Hugo 0.68.3 with theme even" />


<link rel="canonical" href="http://localhost:1313/post/non_cursive_tree_traversal/" />
<link rel="apple-touch-icon" sizes="180x180" href="/apple-touch-icon.png">
<link rel="icon" type="image/png" sizes="32x32" href="/favicon-32x32.png">
<link rel="icon" type="image/png" sizes="16x16" href="/favicon-16x16.png">
<link rel="manifest" href="/manifest.json">
<link rel="mask-icon" href="/safari-pinned-tab.svg" color="#5bbad5">



<link href="/sass/main.min.2e81bbed97b8b282c1aeb57488cc71c8d8c8ec559f3931531bd396bf31e0d4dd.css" rel="stylesheet">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fancyapps/fancybox@3.1.20/dist/jquery.fancybox.min.css" integrity="sha256-7TyXnr2YU040zfSP+rEcz29ggW4j56/ujTPwjMzyqFY=" crossorigin="anonymous">


<meta property="og:title" content="二叉树的非递归遍历" />
<meta property="og:description" content="二叉树的遍历有前序，中序，后序以及层次遍历，其中前序，中序和后序遍历使用递归来写非常简单。
例如


1
2
3
4
5
6
7


void tree_preorder_re(TreeNode *node, Tree *tree, void (*visit)(Tree *, TreeNode *))
{
    if (!node) return;
    visit(tree, node);
    tree_preorder_re(node-&gt;left, tree, visit);
    tree_preorder_re(node-&gt;right, tree, visit);
}


中序和后序，不过是调整一下visit的位置，如果不用递归的写法，改用栈来实现，其实没有那么直观。
首先按照函数调用的关系，入栈的套路都是一样的。


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


    Stack *s = stack_new();
    TreeNode *tNode = tree-&gt;root;
    while (stack_depth(s) != 0 || tNode)
    {
        while (tNode != NULL)
        {
            stack_push(s, tNode);
            tNode = tNode-&gt;left;
        }

        if (!stack_is_empty(s))
        {
            tNode = (TreeNode *)stack_pop(s);
            tNode = tNode-&gt;right;
        }
    }

    stack_free(s);


" />
<meta property="og:type" content="article" />
<meta property="og:url" content="http://localhost:1313/post/non_cursive_tree_traversal/" />
<meta property="article:published_time" content="2021-01-31T00:00:00+00:00" />
<meta property="article:modified_time" content="2021-01-31T00:00:00+00:00" />
<meta itemprop="name" content="二叉树的非递归遍历">
<meta itemprop="description" content="二叉树的遍历有前序，中序，后序以及层次遍历，其中前序，中序和后序遍历使用递归来写非常简单。
例如


1
2
3
4
5
6
7


void tree_preorder_re(TreeNode *node, Tree *tree, void (*visit)(Tree *, TreeNode *))
{
    if (!node) return;
    visit(tree, node);
    tree_preorder_re(node-&gt;left, tree, visit);
    tree_preorder_re(node-&gt;right, tree, visit);
}


中序和后序，不过是调整一下visit的位置，如果不用递归的写法，改用栈来实现，其实没有那么直观。
首先按照函数调用的关系，入栈的套路都是一样的。


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


    Stack *s = stack_new();
    TreeNode *tNode = tree-&gt;root;
    while (stack_depth(s) != 0 || tNode)
    {
        while (tNode != NULL)
        {
            stack_push(s, tNode);
            tNode = tNode-&gt;left;
        }

        if (!stack_is_empty(s))
        {
            tNode = (TreeNode *)stack_pop(s);
            tNode = tNode-&gt;right;
        }
    }

    stack_free(s);


">
<meta itemprop="datePublished" content="2021-01-31T00:00:00&#43;00:00" />
<meta itemprop="dateModified" content="2021-01-31T00:00:00&#43;00:00" />
<meta itemprop="wordCount" content="598">



<meta itemprop="keywords" content="c,data_struct," /><meta name="twitter:card" content="summary"/>
<meta name="twitter:title" content="二叉树的非递归遍历"/>
<meta name="twitter:description" content="二叉树的遍历有前序，中序，后序以及层次遍历，其中前序，中序和后序遍历使用递归来写非常简单。
例如


1
2
3
4
5
6
7


void tree_preorder_re(TreeNode *node, Tree *tree, void (*visit)(Tree *, TreeNode *))
{
    if (!node) return;
    visit(tree, node);
    tree_preorder_re(node-&gt;left, tree, visit);
    tree_preorder_re(node-&gt;right, tree, visit);
}


中序和后序，不过是调整一下visit的位置，如果不用递归的写法，改用栈来实现，其实没有那么直观。
首先按照函数调用的关系，入栈的套路都是一样的。


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


    Stack *s = stack_new();
    TreeNode *tNode = tree-&gt;root;
    while (stack_depth(s) != 0 || tNode)
    {
        while (tNode != NULL)
        {
            stack_push(s, tNode);
            tNode = tNode-&gt;left;
        }

        if (!stack_is_empty(s))
        {
            tNode = (TreeNode *)stack_pop(s);
            tNode = tNode-&gt;right;
        }
    }

    stack_free(s);


"/>

<!--[if lte IE 9]>
  <script src="https://cdnjs.cloudflare.com/ajax/libs/classlist/1.1.20170427/classList.min.js"></script>
<![endif]-->

<!--[if lt IE 9]>
  <script src="https://cdn.jsdelivr.net/npm/html5shiv@3.7.3/dist/html5shiv.min.js"></script>
  <script src="https://cdn.jsdelivr.net/npm/respond.js@1.4.2/dest/respond.min.js"></script>
<![endif]-->

</head>
<body>
  <div id="mobile-navbar" class="mobile-navbar">
  <div class="mobile-header-logo">
    <a href="/" class="logo">lclei</a>
  </div>
  <div class="mobile-navbar-icon">
    <span></span>
    <span></span>
    <span></span>
  </div>
</div>
<nav id="mobile-menu" class="mobile-menu slideout-menu">
  <ul class="mobile-menu-list">
    <a href="/">
        <li class="mobile-menu-item">Home</li>
      </a><a href="/post/">
        <li class="mobile-menu-item">Archives</li>
      </a><a href="/tags/">
        <li class="mobile-menu-item">Tags</li>
      </a><a href="/categories/">
        <li class="mobile-menu-item">Categories</li>
      </a><a href="/about/">
        <li class="mobile-menu-item">About</li>
      </a>
  </ul>

  


</nav>

  <div class="container" id="mobile-panel">
    <header id="header" class="header">
        <div class="logo-wrapper">
  <a href="/" class="logo">lclei</a>
</div>





<nav class="site-navbar">
  <ul id="menu" class="menu">
    <li class="menu-item">
        <a class="menu-item-link" href="/">Home</a>
      </li><li class="menu-item">
        <a class="menu-item-link" href="/post/">Archives</a>
      </li><li class="menu-item">
        <a class="menu-item-link" href="/tags/">Tags</a>
      </li><li class="menu-item">
        <a class="menu-item-link" href="/categories/">Categories</a>
      </li><li class="menu-item">
        <a class="menu-item-link" href="/about/">About</a>
      </li>
  </ul>
</nav>

    </header>

    <main id="main" class="main">
      <div class="content-wrapper">
        <div id="content" class="content">
          <article class="post">
    
    <header class="post-header">
      <h1 class="post-title">二叉树的非递归遍历</h1>

      <div class="post-meta">
        <span class="post-time"> 2021-01-31 </span>
        
        
      </div>
    </header>

    <div class="post-toc" id="post-toc">
  <h2 class="post-toc-title">Contents</h2>
  <div class="post-toc-content always-active">
    <nav id="TableOfContents">
  <ul>
    <li>
      <ul>
        <li><a href="#前序遍历">前序遍历</a></li>
        <li><a href="#中序遍历">中序遍历</a></li>
        <li><a href="#后序遍历">后序遍历</a></li>
      </ul>
    </li>
  </ul>
</nav>
  </div>
</div>
    <div class="post-content">
      <p>二叉树的遍历有前序，中序，后序以及层次遍历，其中前序，中序和后序遍历使用递归来写非常简单。
例如</p>
<div class="highlight"><div class="chroma">
<table class="lntable"><tr><td class="lntd">
<pre class="chroma"><code><span class="lnt">1
</span><span class="lnt">2
</span><span class="lnt">3
</span><span class="lnt">4
</span><span class="lnt">5
</span><span class="lnt">6
</span><span class="lnt">7
</span></code></pre></td>
<td class="lntd">
<pre class="chroma"><code class="language-c" data-lang="c"><span class="kt">void</span> <span class="nf">tree_preorder_re</span><span class="p">(</span><span class="n">TreeNode</span> <span class="o">*</span><span class="n">node</span><span class="p">,</span> <span class="n">Tree</span> <span class="o">*</span><span class="n">tree</span><span class="p">,</span> <span class="kt">void</span> <span class="p">(</span><span class="o">*</span><span class="n">visit</span><span class="p">)(</span><span class="n">Tree</span> <span class="o">*</span><span class="p">,</span> <span class="n">TreeNode</span> <span class="o">*</span><span class="p">))</span>
<span class="p">{</span>
    <span class="k">if</span> <span class="p">(</span><span class="o">!</span><span class="n">node</span><span class="p">)</span> <span class="k">return</span><span class="p">;</span>
    <span class="n">visit</span><span class="p">(</span><span class="n">tree</span><span class="p">,</span> <span class="n">node</span><span class="p">);</span>
    <span class="n">tree_preorder_re</span><span class="p">(</span><span class="n">node</span><span class="o">-&gt;</span><span class="n">left</span><span class="p">,</span> <span class="n">tree</span><span class="p">,</span> <span class="n">visit</span><span class="p">);</span>
    <span class="n">tree_preorder_re</span><span class="p">(</span><span class="n">node</span><span class="o">-&gt;</span><span class="n">right</span><span class="p">,</span> <span class="n">tree</span><span class="p">,</span> <span class="n">visit</span><span class="p">);</span>
<span class="p">}</span>
</code></pre></td></tr></table>
</div>
</div><p>中序和后序，不过是调整一下visit的位置，如果不用递归的写法，改用栈来实现，其实没有那么直观。
首先按照函数调用的关系，入栈的套路都是一样的。</p>
<div class="highlight"><div class="chroma">
<table class="lntable"><tr><td class="lntd">
<pre class="chroma"><code><span class="lnt"> 1
</span><span class="lnt"> 2
</span><span class="lnt"> 3
</span><span class="lnt"> 4
</span><span class="lnt"> 5
</span><span class="lnt"> 6
</span><span class="lnt"> 7
</span><span class="lnt"> 8
</span><span class="lnt"> 9
</span><span class="lnt">10
</span><span class="lnt">11
</span><span class="lnt">12
</span><span class="lnt">13
</span><span class="lnt">14
</span><span class="lnt">15
</span><span class="lnt">16
</span><span class="lnt">17
</span><span class="lnt">18
</span></code></pre></td>
<td class="lntd">
<pre class="chroma"><code class="language-c" data-lang="c">    <span class="n">Stack</span> <span class="o">*</span><span class="n">s</span> <span class="o">=</span> <span class="n">stack_new</span><span class="p">();</span>
    <span class="n">TreeNode</span> <span class="o">*</span><span class="n">tNode</span> <span class="o">=</span> <span class="n">tree</span><span class="o">-&gt;</span><span class="n">root</span><span class="p">;</span>
    <span class="k">while</span> <span class="p">(</span><span class="n">stack_depth</span><span class="p">(</span><span class="n">s</span><span class="p">)</span> <span class="o">!=</span> <span class="mi">0</span> <span class="o">||</span> <span class="n">tNode</span><span class="p">)</span>
    <span class="p">{</span>
        <span class="k">while</span> <span class="p">(</span><span class="n">tNode</span> <span class="o">!=</span> <span class="nb">NULL</span><span class="p">)</span>
        <span class="p">{</span>
            <span class="n">stack_push</span><span class="p">(</span><span class="n">s</span><span class="p">,</span> <span class="n">tNode</span><span class="p">);</span>
            <span class="n">tNode</span> <span class="o">=</span> <span class="n">tNode</span><span class="o">-&gt;</span><span class="n">left</span><span class="p">;</span>
        <span class="p">}</span>

        <span class="k">if</span> <span class="p">(</span><span class="o">!</span><span class="n">stack_is_empty</span><span class="p">(</span><span class="n">s</span><span class="p">))</span>
        <span class="p">{</span>
            <span class="n">tNode</span> <span class="o">=</span> <span class="p">(</span><span class="n">TreeNode</span> <span class="o">*</span><span class="p">)</span><span class="n">stack_pop</span><span class="p">(</span><span class="n">s</span><span class="p">);</span>
            <span class="n">tNode</span> <span class="o">=</span> <span class="n">tNode</span><span class="o">-&gt;</span><span class="n">right</span><span class="p">;</span>
        <span class="p">}</span>
    <span class="p">}</span>

    <span class="n">stack_free</span><span class="p">(</span><span class="n">s</span><span class="p">);</span>
</code></pre></td></tr></table>
</div>
</div><h2 id="前序遍历">前序遍历</h2>
<p>前序遍历最简单，在节点入栈的时候访问。</p>
<div class="highlight"><div class="chroma">
<table class="lntable"><tr><td class="lntd">
<pre class="chroma"><code><span class="lnt"> 1
</span><span class="lnt"> 2
</span><span class="lnt"> 3
</span><span class="lnt"> 4
</span><span class="lnt"> 5
</span><span class="lnt"> 6
</span><span class="lnt"> 7
</span><span class="lnt"> 8
</span><span class="lnt"> 9
</span><span class="lnt">10
</span><span class="lnt">11
</span><span class="lnt">12
</span><span class="lnt">13
</span><span class="lnt">14
</span><span class="lnt">15
</span><span class="lnt">16
</span><span class="lnt">17
</span><span class="lnt">18
</span><span class="lnt">19
</span><span class="lnt">20
</span><span class="lnt">21
</span><span class="lnt">22
</span></code></pre></td>
<td class="lntd">
<pre class="chroma"><code class="language-c" data-lang="c"><span class="kt">void</span> <span class="nf">tree_preorder</span><span class="p">(</span><span class="n">Tree</span> <span class="o">*</span><span class="n">tree</span><span class="p">,</span> <span class="kt">void</span> <span class="p">(</span><span class="o">*</span><span class="n">visit</span><span class="p">)(</span><span class="n">Tree</span> <span class="o">*</span><span class="p">,</span> <span class="n">TreeNode</span> <span class="o">*</span><span class="p">))</span>
<span class="p">{</span>
    <span class="n">Stack</span> <span class="o">*</span><span class="n">s</span> <span class="o">=</span> <span class="n">stack_new</span><span class="p">();</span>
    <span class="n">TreeNode</span> <span class="o">*</span><span class="n">tNode</span> <span class="o">=</span> <span class="n">tree</span><span class="o">-&gt;</span><span class="n">root</span><span class="p">;</span>
    <span class="k">while</span> <span class="p">(</span><span class="n">stack_depth</span><span class="p">(</span><span class="n">s</span><span class="p">)</span> <span class="o">!=</span> <span class="mi">0</span> <span class="o">||</span> <span class="n">tNode</span><span class="p">)</span>
    <span class="p">{</span>
        <span class="k">while</span> <span class="p">(</span><span class="n">tNode</span> <span class="o">!=</span> <span class="nb">NULL</span><span class="p">)</span>
        <span class="p">{</span>
            <span class="n">stack_push</span><span class="p">(</span><span class="n">s</span><span class="p">,</span> <span class="n">tNode</span><span class="p">);</span>
            <span class="n">visit</span><span class="p">(</span><span class="n">tree</span><span class="p">,</span> <span class="n">tNode</span><span class="p">);</span>
            <span class="n">tNode</span> <span class="o">=</span> <span class="n">tNode</span><span class="o">-&gt;</span><span class="n">left</span><span class="p">;</span>
        <span class="p">}</span>

        <span class="k">if</span> <span class="p">(</span><span class="o">!</span><span class="n">stack_is_empty</span><span class="p">(</span><span class="n">s</span><span class="p">))</span>
        <span class="p">{</span>
            <span class="n">tNode</span> <span class="o">=</span> <span class="p">(</span><span class="n">TreeNode</span> <span class="o">*</span><span class="p">)</span><span class="n">stack_pop</span><span class="p">(</span><span class="n">s</span><span class="p">);</span>
            <span class="n">tNode</span> <span class="o">=</span> <span class="n">tNode</span><span class="o">-&gt;</span><span class="n">right</span><span class="p">;</span>
        <span class="p">}</span>
    <span class="p">}</span>

    <span class="n">stack_free</span><span class="p">(</span><span class="n">s</span><span class="p">);</span>
<span class="p">}</span>
</code></pre></td></tr></table>
</div>
</div><h2 id="中序遍历">中序遍历</h2>
<p>在节点出栈的时候访问。</p>
<div class="highlight"><div class="chroma">
<table class="lntable"><tr><td class="lntd">
<pre class="chroma"><code><span class="lnt"> 1
</span><span class="lnt"> 2
</span><span class="lnt"> 3
</span><span class="lnt"> 4
</span><span class="lnt"> 5
</span><span class="lnt"> 6
</span><span class="lnt"> 7
</span><span class="lnt"> 8
</span><span class="lnt"> 9
</span><span class="lnt">10
</span><span class="lnt">11
</span><span class="lnt">12
</span><span class="lnt">13
</span><span class="lnt">14
</span><span class="lnt">15
</span><span class="lnt">16
</span><span class="lnt">17
</span><span class="lnt">18
</span><span class="lnt">19
</span><span class="lnt">20
</span><span class="lnt">21
</span></code></pre></td>
<td class="lntd">
<pre class="chroma"><code class="language-c" data-lang="c"><span class="kt">void</span> <span class="nf">tree_inorder</span><span class="p">(</span><span class="n">Tree</span> <span class="o">*</span><span class="n">tree</span><span class="p">,</span> <span class="kt">void</span> <span class="p">(</span><span class="o">*</span><span class="n">visit</span><span class="p">)(</span><span class="n">Tree</span> <span class="o">*</span><span class="p">,</span> <span class="n">TreeNode</span> <span class="o">*</span><span class="p">))</span>
<span class="p">{</span>
    <span class="n">Stack</span> <span class="o">*</span><span class="n">s</span> <span class="o">=</span> <span class="n">stack_new</span><span class="p">();</span>
    <span class="n">TreeNode</span> <span class="o">*</span><span class="n">tNode</span> <span class="o">=</span> <span class="n">tree</span><span class="o">-&gt;</span><span class="n">root</span><span class="p">;</span>
    <span class="k">while</span><span class="p">(</span><span class="n">stack_depth</span><span class="p">(</span><span class="n">s</span><span class="p">)</span> <span class="o">!=</span> <span class="mi">0</span> <span class="o">||</span> <span class="n">tNode</span> <span class="o">!=</span> <span class="nb">NULL</span><span class="p">)</span>
    <span class="p">{</span>
        <span class="k">while</span> <span class="p">(</span><span class="n">tNode</span> <span class="o">!=</span> <span class="nb">NULL</span><span class="p">)</span>
        <span class="p">{</span>
            <span class="n">stack_push</span><span class="p">(</span><span class="n">s</span><span class="p">,</span> <span class="n">tNode</span><span class="p">);</span>
            <span class="n">tNode</span> <span class="o">=</span> <span class="n">tNode</span><span class="o">-&gt;</span><span class="n">left</span><span class="p">;</span>
        <span class="p">}</span>

        <span class="k">if</span> <span class="p">(</span><span class="o">!</span><span class="n">stack_is_empty</span><span class="p">(</span><span class="n">s</span><span class="p">))</span>
        <span class="p">{</span>
            <span class="n">tNode</span> <span class="o">=</span> <span class="p">(</span><span class="n">TreeNode</span> <span class="o">*</span><span class="p">)</span><span class="n">stack_pop</span><span class="p">(</span><span class="n">s</span><span class="p">);</span>
            <span class="n">visit</span><span class="p">(</span><span class="n">tree</span><span class="p">,</span> <span class="n">tNode</span><span class="p">);</span>
            <span class="n">tNode</span> <span class="o">=</span> <span class="n">tNode</span><span class="o">-&gt;</span><span class="n">right</span><span class="p">;</span>
        <span class="p">}</span>
    <span class="p">}</span>
    <span class="n">stack_free</span><span class="p">(</span><span class="n">s</span><span class="p">);</span>
<span class="p">}</span>
</code></pre></td></tr></table>
</div>
</div><h2 id="后序遍历">后序遍历</h2>
<p>保证左右节点都访问之后，再访问父节点。</p>
<div class="highlight"><div class="chroma">
<table class="lntable"><tr><td class="lntd">
<pre class="chroma"><code><span class="lnt"> 1
</span><span class="lnt"> 2
</span><span class="lnt"> 3
</span><span class="lnt"> 4
</span><span class="lnt"> 5
</span><span class="lnt"> 6
</span><span class="lnt"> 7
</span><span class="lnt"> 8
</span><span class="lnt"> 9
</span><span class="lnt">10
</span><span class="lnt">11
</span><span class="lnt">12
</span><span class="lnt">13
</span><span class="lnt">14
</span><span class="lnt">15
</span><span class="lnt">16
</span><span class="lnt">17
</span><span class="lnt">18
</span><span class="lnt">19
</span><span class="lnt">20
</span><span class="lnt">21
</span><span class="lnt">22
</span><span class="lnt">23
</span><span class="lnt">24
</span><span class="lnt">25
</span><span class="lnt">26
</span><span class="lnt">27
</span><span class="lnt">28
</span><span class="lnt">29
</span><span class="lnt">30
</span><span class="lnt">31
</span><span class="lnt">32
</span></code></pre></td>
<td class="lntd">
<pre class="chroma"><code class="language-c" data-lang="c"><span class="kt">void</span> <span class="nf">tree_postorder</span><span class="p">(</span><span class="n">Tree</span> <span class="o">*</span><span class="n">tree</span><span class="p">,</span> <span class="kt">void</span> <span class="p">(</span><span class="o">*</span><span class="n">visit</span><span class="p">)(</span><span class="n">Tree</span> <span class="o">*</span><span class="p">,</span> <span class="n">TreeNode</span> <span class="o">*</span><span class="p">))</span>
<span class="p">{</span>
    <span class="n">Stack</span> <span class="o">*</span><span class="n">s</span> <span class="o">=</span> <span class="n">stack_new</span><span class="p">();</span>
    <span class="n">TreeNode</span> <span class="o">*</span><span class="n">tNode</span> <span class="o">=</span> <span class="n">tree</span><span class="o">-&gt;</span><span class="n">root</span><span class="p">;</span>
    <span class="n">TreeNode</span> <span class="o">*</span><span class="n">last_visit</span> <span class="o">=</span> <span class="nb">NULL</span><span class="p">;</span>
    <span class="k">while</span><span class="p">(</span><span class="n">tNode</span> <span class="o">!=</span> <span class="nb">NULL</span> <span class="o">||</span> <span class="o">!</span><span class="n">stack_is_empty</span><span class="p">(</span><span class="n">s</span><span class="p">))</span>
    <span class="p">{</span>
        <span class="k">while</span> <span class="p">(</span><span class="n">tNode</span> <span class="o">!=</span> <span class="nb">NULL</span><span class="p">)</span>
        <span class="p">{</span>
            <span class="n">stack_push</span><span class="p">(</span><span class="n">s</span><span class="p">,</span> <span class="n">tNode</span><span class="p">);</span>
            <span class="n">tNode</span> <span class="o">=</span> <span class="n">tNode</span><span class="o">-&gt;</span><span class="n">left</span><span class="p">;</span>
        <span class="p">}</span>

        <span class="k">if</span> <span class="p">(</span><span class="o">!</span><span class="n">stack_is_empty</span><span class="p">(</span><span class="n">s</span><span class="p">))</span>
        <span class="p">{</span>
            <span class="n">tNode</span> <span class="o">=</span> <span class="p">(</span><span class="n">TreeNode</span> <span class="o">*</span><span class="p">)</span><span class="n">stack_top</span><span class="p">(</span><span class="n">s</span><span class="p">);</span>
            <span class="k">if</span> <span class="p">(</span><span class="n">tNode</span><span class="o">-&gt;</span><span class="n">right</span> <span class="o">==</span> <span class="nb">NULL</span> <span class="o">||</span> <span class="n">tNode</span><span class="o">-&gt;</span><span class="n">right</span> <span class="o">==</span> <span class="n">last_visit</span><span class="p">)</span>
            <span class="p">{</span>
                <span class="n">stack_pop</span><span class="p">(</span><span class="n">s</span><span class="p">);</span>
                <span class="n">last_visit</span> <span class="o">=</span> <span class="n">tNode</span><span class="p">;</span>
                <span class="n">visit</span><span class="p">(</span><span class="n">tree</span><span class="p">,</span> <span class="n">tNode</span><span class="p">);</span>
                <span class="n">tNode</span> <span class="o">=</span> <span class="nb">NULL</span><span class="p">;</span>
            <span class="p">}</span>
            <span class="k">else</span>
            <span class="p">{</span>
                <span class="n">tNode</span> <span class="o">=</span> <span class="n">tNode</span><span class="o">-&gt;</span><span class="n">right</span><span class="p">;</span>
            <span class="p">}</span>
            
        <span class="p">}</span>
    <span class="p">}</span>
    <span class="n">stack_free</span><span class="p">(</span><span class="n">s</span><span class="p">);</span>
<span class="p">}</span>
</code></pre></td></tr></table>
</div>
</div><p>验证</p>
<div class="highlight"><div class="chroma">
<table class="lntable"><tr><td class="lntd">
<pre class="chroma"><code><span class="lnt"> 1
</span><span class="lnt"> 2
</span><span class="lnt"> 3
</span><span class="lnt"> 4
</span><span class="lnt"> 5
</span><span class="lnt"> 6
</span><span class="lnt"> 7
</span><span class="lnt"> 8
</span><span class="lnt"> 9
</span><span class="lnt">10
</span><span class="lnt">11
</span><span class="lnt">12
</span></code></pre></td>
<td class="lntd">
<pre class="chroma"><code class="language-fallback" data-lang="fallback">main(251): __debug preorder recursive---
1 2 4 5 3 6 7 
main(254): __debug preorder non-recursive---
1 2 4 5 3 6 7 
main(257): __debug inorder recursive---
4 2 5 1 6 3 7 
main(260): __debug inorder non-recursive---
4 2 5 1 6 3 7 
main(263): __debug postorder recursive---
4 5 2 6 7 3 1 
main(266): __debug postorder non_ecursive---
4 5 2 6 7 3 1
</code></pre></td></tr></table>
</div>
</div>
    </div>

    <div class="post-copyright">
  <p class="copyright-item">
    <span class="item-title">Author</span>
    <span class="item-content">lclei</span>
  </p>
  <p class="copyright-item">
    <span class="item-title">LastMod</span>
    <span class="item-content">
        2021-01-31
        
    </span>
  </p>
  
  
</div>
<footer class="post-footer">
      <div class="post-tags">
          <a href="/tags/c/">c</a>
          <a href="/tags/data_struct/">data_struct</a>
          </div>
      <nav class="post-nav">
        <a class="prev" href="/post/hugo_and_git_submodule/">
            <i class="iconfont icon-left"></i>
            <span class="prev-text nav-default">Hugo and git submodule</span>
            <span class="prev-text nav-mobile">Prev</span>
          </a>
        <a class="next" href="/post/udisk-grub/">
            <span class="next-text nav-default">使用grub创建多系统u盘安装盘</span>
            <span class="next-text nav-mobile">Next</span>
            <i class="iconfont icon-right"></i>
          </a>
      </nav>
    </footer>
  </article>
        </div>
        

  

  

      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="social-links">
      <a href="mailto:lclei@mail.ustc.edu.cn" class="iconfont icon-email" title="email"></a>
      <a href="https://gitee.com/lclei" class="iconfont icon-gitee" title="gitee"></a>
      <a href="https://gitee.com/lclei" class="iconfont icon-github" title="github"></a>
  <a href="http://localhost:1313/index.xml" type="application/rss+xml" class="iconfont icon-rss" title="rss"></a>
</div>

<div class="copyright">
  <span class="power-by">
    Powered by <a class="hexo-link" href="https://gohugo.io">Hugo</a>
  </span>
  <span class="division">|</span>
  <span class="theme-info">
    Theme - 
    <a class="theme-link" href="https://github.com/olOwOlo/hugo-theme-even">Even</a>
  </span>

  

  <span class="copyright-year">
    &copy; 
    2018 - 
    2022<span class="heart"><i class="iconfont icon-heart"></i></span><span>lclei</span>
  </span>
</div>

    </footer>

    <div class="back-to-top" id="back-to-top">
      <i class="iconfont icon-up"></i>
    </div>
  </div>
  
  <script src="https://cdn.jsdelivr.net/npm/jquery@3.2.1/dist/jquery.min.js" integrity="sha256-hwg4gsxgFZhOsEEamdOYGBf13FyQuiTwlAQgxVSNgt4=" crossorigin="anonymous"></script>
  <script src="https://cdn.jsdelivr.net/npm/slideout@1.0.1/dist/slideout.min.js" integrity="sha256-t+zJ/g8/KXIJMjSVQdnibt4dlaDxc9zXr/9oNPeWqdg=" crossorigin="anonymous"></script>
  <script src="https://cdn.jsdelivr.net/npm/@fancyapps/fancybox@3.1.20/dist/jquery.fancybox.min.js" integrity="sha256-XVLffZaxoWfGUEbdzuLi7pwaUJv1cecsQJQqGLe7axY=" crossorigin="anonymous"></script>



<script type="text/javascript" src="/js/main.min.c12618f9a600c40bd024996677e951e64d3487006775aeb22e200c990006c5c7.js"></script>








</body>
</html>
